Communication switch systems, such as 1PSS packet switch systems manufactured and used by AT&T, are typically interconnected either by a single trunk or a group of trunks known as a trunk group. Each trunk may provide hundreds of virtual circuit call connections at a time. For packet switch systems interconnected by a trunk group, a known distribution method has been used to distribute the packet traffic among the trunks of the group. Recently, a problem has been uncovered with this known distribution method during the operation of multiple 1PSS switch systems connected by trunk groups. The known distribution method works well for trunk groups having a power of two, e.g. 2, 4 and 8, as the number of trunks in the group. For trunk groups having a number that was not a power of two, e.g., 3, 5, 6, and 7, on the other hand, the known distribution method was unexpectedly found to be highly inefficient. For these latter trunk groups, as the number of trunks in the group increased the known distribution method was found to be increasingly ineffective.
Each 1PSS switch system is designed to have a maximum of eight trunks per trunk group interconnecting it to another 1PSS switch system. The known distribution method is based upon the maximum number of trunks. Trunks in a group are indexed according to their ID (between 0 and M-1), where M is the number of trunks in the group. The known method for routing traffic over the trunks of a group works as follows: In each switch, and for every trunk group there exists a trunk group table with 8 index entries. Starting at index position 0, the entries in the table are filled in with the trunk IDs of active trunks of the trunk group from 0 to M-1. If M is less than 8 but greater than or equal to 4, then starting at index position M, the filling-in process starts over again with trunk ID=0, and so on, until all 8 trunk ID entries in the table are filled in. If M is less than four, then the filling process starts over again at M, 2M and so forth. Table I below gives an example of the known method for M=2 and Table H gives an example of the known method for M=3,
TABLE I ______________________________________ Trunk Group Size = 2 ______________________________________ Index 0 1 2 3 4 5 6 7 Trunk ID 0 1 0 1 0 1 0 1 ______________________________________
TABLE II ______________________________________ Trunk Group Size = 3 ______________________________________ Index 0 1 2 3 4 5 6 7 Trunk ID 0 1 2 0 1 2 0 1 ______________________________________
During call processing, the packet switch associates a call-id with every virtual circuit set up for every call. The call-id modulo 32 is stored in a 5 bit field, referred to as the balance field, in an internal protocol packet header. Internal protocol is the protocol used for communication between the packet switches. Communication between a packet and any external devices, on the other hand, is by X.25 protocol. The 5-bit call-id is Subsequently divided modulo 8 and the remainder used as an index into the trunk group table in order to select a trunk of the trunk group.
Depending on the trunk group size, the traffic may or may not be evenly distributed across the group, as shown for trunk groups of sizes 2 and 3 above. For packet systems having large amounts of traffic, an uneven distribution in the trunk group table results in the trunk or trunks with the greater number of number entries in the trunk group table being filled to capacity, while the trunk or trunks with the lesser number of entries are less than full. This uneven distribution reduces the effective bandwidth and the packet carrying efficiency of the trunk group. This is shown in TABLE III, which presents the maximum trunk and trunk group efficiencies for the known trunk distribution method. In calculating these efficiencies, the number of calls distributed by each packet switch was assumed to be large, i.e. many simultaneous calls on each trunk.
TABLE III ______________________________________ No. of Util. Of Number No. of Partially Partially Effective Average of Trks. Full Filled Filled Bandwidth Group per Group Trunks Trks. Trks. per Grp. Effncy ______________________________________ 1 1 0 -- 1 1 2 2 0 -- 2 1 3 2 1 0.667 2.667 .88 4 4 0 -- 4 1 5 3 2 0.5 4 0.8 6 2 4 0.5 4 0.667 7 1 6 0.5 4 0.571 8 8 0 -- 8 1 ______________________________________
The average trunk group efficiency; the last column of TABLE III, is calculated as follows for a group of size M:
c is the average number of active calls on a trunk group over a given time interval T; PA1 c.sub.i is the average number of active calls on trunk i in the trunk group over the same time interval T. PA1 m=max c.sub.i ; and PA1 average trunk group efficiency=c/(mM).
For the purposes of the calculations shown in Table III, it was also assumed that call arrival, duration, and destination patterns were random, and that the interval T tends to infinity.
If the effective bandwidth of a group, i.e., (trunk group size).times.(average trunk efficiency), is considered, the known distribution method yields an effective bandwidth of four trunks known per group for trunk group sizes 4, 5, 6, and 7. This means that using the known distribution method, trunk group call capacity does not increase until the number of trunks in a trunk group increases from 4 to 8. Furthermore, with the known trunk group distribution method if a trunk group with 8 trunks loses the operation of one of those trunks because of equipment problems, the overall trunk group capacity is reduced by one half with the loss of one eighth of its trunks.
The data of Table III show that trunk group inefficiencies occur where the number of trunks in a trunk group is not a factor, i.e., a sub-multiple, of the number of indices of the trunk group table.
Considering the anticipated growth of inter-switch traffic because of growth in consolidation of packet traffic, there is a need in the art for a distribution method that allows for growing trunk groups incrementally without suffering the inefficiencies of the known method. Similarly, since trunk group size reductions, either from equipment problems or local consolidations, are not unknown, there is also a need in the art for a trunk distribution method that allows incremental reductions of trunk group size, without incurring the substantial inefficiencies of the known method.
It is an object of the present invention to provide a distribution method that has a number of indices of a trunk group table that is a multiple of the number of trunks in a trunk group.
It is another object of the invention to provide an efficient apparatus for distributing calls among trunks of a trunk group between packet switch systems.
It is another object of the invention to provide a method for maintaining an even call distribution when one or more trunks are added to or deleted from an in service trunk group.